/*************************************************************************
	> File Name: longestsubstr.cpp
	> Author: likang
	> Mail: likang@ict.ac.cn
	> Created Time: 一  9/18 19:28:01 2017
 ************************************************************************/

#include<iostream>
#include<string>
#include<vector>

using namespace std;

// 最长公共子串
// max[i][j] 代表以 s1 中第 i 个字符与 s2 中第 j 个字符结尾的公共子串长度（包含 s1[i] s2[j]）
string longestsubstr(string &s1, string &s2) {
    int len1 = s1.length();
    int len2 = s2.length();

    int max[len1 + 1][len2 + 1];
    int res = 0;
    int end1;
    int end2;

    bzero(max, (len1 + 1) * (len2 + 1) * sizeof(int));

    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                max[i][j] = max[i - 1][j - 1] + 1;
            } else {
                max[i][j] = 0;
            }
            if (max[i][j] > res) {
                res = max[i][j];
                end1 = i;
                end2 = j;
            }
        }
    }
    cout << res << endl;
    return s1.substr(end1 - res, res);
}

// 最长公共子序列
// max[i][j] 代表 s1 中第 i 个字符与 s2 中第 j 个字符结尾的公共子序列长度（可不包含s1[i] s2[j]）
string longestsubseq(string &s1, string &s2) {
    
    int len1 = s1.length();
    int len2 = s2.length();

    int max[len1 + 1][len2 + 1];
    bzero(max, (len1 + 1) * (len2 + 1) * sizeof(int));

    string res;
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                max[i][j] = max[i - 1][j - 1] + 1;
            } else {
                max[i][j] = max[i - 1][j] > max[i][j - 1] ? max[i - 1][j] : max[i][j - 1];
            }
        }
    }
    cout << max[len1][len2] << endl;
    int left = len1;
    int right = len2;

    for (int i = 0; i < max[len1][len2]; ++i) {
        if (max[left][right] == max[left - 1][right]) {
            --i;
            --left;
        } else if (max[left][right] == max[left][right - 1]) {
            --i;
            --right;
        } else {
            --left;
            --right;
            res = s1[left] + res;
        }
    }
    
    return res;
}

// 最长递增子数组

vector<int> longestAscArray(vector<int> &vec) {
    int num = vec.size();
    int max[num];
    max[0] = 1;
    int max_length = 0;
    int point;

    for (int i = 1; i < num; ++i) {
        if (vec[i] >= vec[i - 1]) {
            max[i] = max[i - 1] + 1;
        } else {
            max[i] = 1;
        }
        if (max[i] > max_length) {
            max_length = max[i];
            point = i;
        }
    }

    vector<int> res;
    cout << max_length << endl;
    for (int i = max_length; i > 0; --i) {
        res.push_back(vec[point - i + 1]);
    }
    return res;
}

// 最长递增子序列
vector<int> longestAscSeq(vector<int> &vec) {
    int num = vec.size();
    int max[num];
    bzero(max, num * sizeof(int));
    max[0] = 1;
    int res = 0;
    int point;

    for (int i = 1; i < num; ++i) {
        max[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (vec[i] >= vec[j] && max[j] + 1 > max[i]) {
                max[i] = max[j] + 1;
            }
        }
        if (max[i] > res) {
            res = max[i];
            point = i;
        }
    }
    cout << res << endl;
    vector<int> haha;
    haha.push_back(vec[point]);

    for (int i = 1; i < res; ++i) {
        int tmp = 1;
        while (true) {
            if (max[point] == max[point - tmp] + 1) {
                haha.push_back(vec[point - tmp]);
                point -= tmp;
                break;
            }
            ++tmp;
        }

    }
    return haha;
}
// 最大子数组之和
int largestSubArray(vector<int> &vec) {
    int num = vec.size();

    int max[num];
    max[0] = vec[0];
    int res = max[0];

    for (int i = 1; i < num; ++i) {
        if (max[i - 1] > 0) {
            max[i] = max[i - 1] + vec[i];
        } else {
            max[i] = vec[i];
        
        }
        if (max[i] > res) {
            res = max[i];
        }
    
    }
    return res;
}
// 最大子序列之和
// 所有正数相加即可

int main(void) {
    string s1 = "abcdefg";
    string s2 = "bdefgcde";

    cout << longestsubstr(s1, s2) << endl;
    cout << longestsubseq(s1, s2) << endl;
    int arr[] = {6, 5, 1, 3, -6, 4, 5, 2};
    vector<int> vec(arr, arr + sizeof(arr) / sizeof(int));
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    vector<int> res = longestAscArray(vec);
    for (auto it = res.begin(); it != res.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    res = longestAscSeq(vec);
    for (auto it = res.begin(); it != res.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    cout << largestSubArray(vec) << endl;
    return 0;
}

